The present invention relates generally to a variable length coding and/or decoding system used for compression coding and/or decoding moving picture signals or the like. More specifically, the invention relates to a variable length coding and/or decoding system capable of decoding both in forward and backward directions, and a recording medium for recording data or programs for use in the system.
A variable length code is a code system of a short code length on average, which is obtained by assigning a short code length of codes to a frequently appearing symbol and a long code length of codes to a rarely appearing symbol on the basis of the appearance frequency of symbols. Therefore, if a variable length code is used, the amount of data can be considerably compressed in comparison with the amount of data before being coded. As a method for forming such a variable length code, the Huffman algorithm suitable for memoryless sources is known.
In general, there is a problem in that, if an error is mixed in a variable length code due to a channel error of coded data or the like, a decoding system can not correctly decode the data due to the propagation of influence of the error after the error is mixed therein. In order to avoid this problem, there is a typical method for inserting synchronization patterns at intervals to prevent the propagation of an error when there is a possibility that the error may occur in a channel. Bit patterns, which do not appear by any combinations of variable length codes, are assigned to the synchronization patterns. According to this method, even if coded data can not be decoded due to an error occurring therein, it is possible to prevent the propagation of the error to correctly decode the coded data by finding the next synchronization pattern.
However, even if the synchronization patterns are used, the coded data can not be decoded until the next synchronization pattern is found from the position, at which the coded data can not be correctly decoded due to the error occurring therein as shown in FIG. 1A.
Therefore, there is known a method for changing the variable length codes from the usual configurations shown in FIGS. 2A through 2C to the configurations shown in FIGS. 3A through 3C to form code words, which can be decoded in a usual forward direction as well as in a backward direction as shown in FIG. 1B. Since the coded data of such code words are also readable in the backward direction, the code words can be also used for reverse reproduction in a storage medium, such as a disc memory, for storing the coded data. This variable length code, which can be decoded in the forward direction as well as in the backward direction, will be hereinafter referred to as a "reversible code".
An example of the reversible code is disclosed in Japanese Patent Laid-Open No. 5-300027, entitled "Reversible Variable Length Coding System". This publicly-known reversible code is a variable length code, which can also be decoded in the backward direction by adding bits to the ends of code words of a Huffman code, which is a variable code capable of being decoded in the forward direction as shown in FIGS. 2A through 2C, so that the respective code words are not coincident with other code words having longer code lengths as shown in FIGS. 3A through 3C. However, this reversible code contains many useless bits to have a long average code length since the bits are added to the ends of the code words of the variable length code, which can be decoded only in the forward direction. Consequently, the coding efficiency is considerably deteriorated in comparison with the variable length code, which can be decoded only in the forward direction.
There is also a problem in that the conventional reversible code can not be decoded in the backward direction if synchronization intervals are set every predetermined interval. For example, ITU-T H.263 (1996) can align synchronization patterns every 8 bits (=1 byte), i.e., it can set positions, at which the synchronization patterns can be inserted, every 1 byte. In order to realize such alignment of synchronization intervals, stuffing codes shown in FIG. 34 are inserted before the synchronization patterns. In such a case, in the conventional reversible codes, there is a problem in that the backward decoding can not be carried out due to the stuffing bits.
Moreover, when the reversible code is simply decoded, there is a problem in that the circuit scale and the amount of operation have to be twice as large as those in a usual decoding system for variable length codes, which can be decoded only in the forward direction, by the amount decoded in the backward direction.
There is another problem in that the conventional reversible code can not be decoded in the backward direction by syntax of input information as the case may be. For example, in the case of source symbols having syntax shown in FIG. 5A, the sign of symbol B is determined by symbol A. Coded data obtained by coding source symbols having such syntax can not be decoded in the backward direction since the symbol B can not be decoded unless the symbol A has been decoded as shown in FIG. 5B.
As a coding system used when the number of source symbols is high, there is a system using escape codes. This system using escape codes has code words corresponding to a small number of source symbols having a high appearance frequency as a code-word table, and encodes a large majority of source symbols having a low appearance frequency by the combinations of escape codes and fixed length codes. Also in this system using escape codes, there has been provided a system for applying escape codes to the prefix and suffix of a variable length code, similar to the variable length code capable of being decoded both in the forward and backward directions.
In the conventional coding and/or decoding system using escape codes, it is required to search the code-word table for the presence of code words in order to distinguish the code words existing in the code-word table from the code words to be coded using escape codes.
That is, as described above, since the conventional reversible code, i.e., the variable length code capable of being decoded both in the forward and backward directions, is formed by adding bits to the suffix of code words of a variable length code capable of being decoded only in the forward direction, there is a problem in that useless bit patterns are increased to increase an average code length, so that the coding efficiency is considerably deteriorated in comparison with the variable length code capable of being decoded only in the forward direction. In addition, if the synchronization intervals are set every predetermined intervals using stuffing bits, there is a problem in that the reversible code can not be decoded in the backward direction due to the stuffing bits. Moreover, if the reversible code is simply decoded, there is a problem in that the circuit scale and the amount of operation have to be twice as large as those in a usual decoding system for variable length codes capable of being decoded only in the forward direction, by the amount decoded in the backward direction, and there is a problem in that it is not possible to decode in the backward direction by the syntax of input information as the case may be.